package algorithm7.leetcode.hot100.c3滑动窗口;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class h8_LC3无重复字符的最长子串 {

/*

https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked3
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

 */

    class Solution {
        public int lengthOfLongestSubstring(String s) {
            return handle1(s);
        }

        // 滑窗
        private int handle1(String s) {
            char[] chars = s.toCharArray();
            int l = 0, r = 0, n = chars.length;
            Set<Character> set = new HashSet<>();
            int max = 0;
            while (r < n) {
                if (!set.contains(chars[r])) {
                    set.add(chars[r]);
                    max = Math.max(max, r - l + 1);
                    r++;
                } else {
                    while (chars[l] != chars[r]) {
                        set.remove(chars[l]);
                        l++;
                    }
                    l++;
                    r++;
                }
            }

            return max;
        }
    }

//    char[] chars = s.toCharArray();
//    int n = chars.length;
//    int maxLen = 0;
//    int r = 0;
//    int l = 0;
//    HashSet<Character> set = new HashSet<>();
//        while (r < n) {
//        if (set.contains(chars[r])) {
//            while (chars[l] != chars[r]) {
//                set.remove(chars[l]);
//                l++;
//            }
//            r++;
//            l++;
//        } else {
//            set.add(chars[r]);
//            maxLen = Math.max(maxLen, r - l + 1);
//            r++;
//        }
//    }

    @Test
    void test() {
        String s = "abcabcbb";
        int ans = new Solution().lengthOfLongestSubstring(s);
        System.out.println("ans = " + ans);
    }

}
